#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/11 15:01
# @Author  : Yuyun
# @File    : 迭代遍历.py
# @IDE     : PyCharm
from collections import deque
class TreeNode:
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right
#   使用栈实现迭代的效果
class Solution:
    """
    前序遍历：中-左-右
    """
    def preorder_traversal(self, root:TreeNode):
        res = []
        if root is None:
            return
        stack = [root]
        while stack:
            node = stack.pop()
            if node != None:
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
                stack.append(node)
                #   中节点访问过，但是还没有处理，加入空节点做为标记。
                stack.append(None)
            else:#  只有遇到空节点的时候，才将下一个节点放进结果集
                node = stack.pop()
                res.append(node.val)
        return res
    """
    中序遍历：左-中-右
    """
    def midorder_traversal(self, root:TreeNode):
        res = []
        if root is None:
            return
        stack = [root]
        while stack:
            node = stack.pop()
            if node != None:
                if node.right:
                    stack.append(node.right)
                stack.append(node)
                stack.append(None)
                if node.left:
                    stack.append(node.left)
            else:
                node = stack.pop()
                res.append(node.val)
        return res
    """
    后序遍历：左-右-中
    """
    def postorder_traveral(self, root:TreeNode):
        result = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                st.append(node)  # 中
                st.append(None)
                if node.right:  # 右
                    st.append(node.right)
                if node.left:  # 左
                    st.append(node.left)
            else:
                node = st.pop()
                result.append(node.val)
        return result
    """
    层序遍历：BFS
    """
    def levelorder_traversal(self, root:TreeNode):
        if root is None:
            return
        queue = deque([root])
        res = []
        while queue:
            #   存储每层节点
            level = []
            #   遍历每层，双端队列加入每层节点的左右字节点
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(level)
        return res